/*
 * Copyright 北京航空航天大学  @ 2015 版权所有
 */
package com.buaa.edu.leetcode.algorithm.array;

import org.junit.Test;

/**
 * <p>
 * 两排序数组合并后的中值
 * 要求时间复杂度O(log (m+n)).
 * </p>
 * @author towan
 * @email tongwenzide@163.com
 * @time 2015年6月21日
 */
public class MedianOfTwoSortedArrays {

  public double findMedianSortedArrays(int[] nums1, int[] nums2) {
      if((nums1==null || nums1.length==0) && (nums2==null || nums2.length==0)){
          return 0.0;
      }
      int m = nums1.length;
      int n = nums2.length;
      int k = (n+m-1)/2+1;
      return findMedianSortedArrays(nums1, nums2,k);
   
  }

    /**
     * @param nums1
     * @param nums2
     * @param k
     * @return
     * @author towan 2015年6月21日
     */
    private double findMedianSortedArrays(int[] nums1, int[] nums2, int k) {
        int m = nums1.length;
        int n = nums2.length;
        if (m > n) {
            return findMedianSortedArrays(nums2, nums1, k);
        }
        int left = 0;
        int right = m;
        while (left < right) {
            int mid = left + (right - left) / 2;
            int j = k - 1 - mid;
            if (j >= n || nums1[mid] < nums2[j]) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        int ai = left - 1 >= 0 ? nums1[left - 1] : Integer.MIN_VALUE;
        int bj = k - 1 - left >= 0 ? nums2[k - 1 - left] : Integer.MIN_VALUE;
        int valK = Math.max(ai, bj);
        if ((m + n) % 2 == 1) {
            return valK;
        }
        // 如果两个数组元素的总数是偶数，则取第k和k+1的均值
        int bjplus = k - left >= n ? Integer.MAX_VALUE : nums2[k - left];
        int arri = left >= m ? Integer.MAX_VALUE : nums1[left];
        return (double) (valK + Math.min(bjplus, arri)) / 2;
    }
    @Test
    public void testCaseOne(){
        int nums1[] = {1,1};
        int nums2[] = {1,2};
        double medianVal = findMedianSortedArrays(nums1,nums2);
        System.out.println(medianVal);
    }
    
}
